МЕТОДЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Данные методы используются для решения задач математического программирования, позволяющих представлять их в виде нескольких менее сложных подзадач с одной целевой функцией.
Динамическое программирование особенно эффективно для задач, условия которых позволяют составить сетевой график перехода от этапа к этапу, где узлы сети будут соответствовать различным значениям переменных, а дуги — допустимым вариантам решения (см. [6.51]).
Основным принципом, положенным в основу метода динамического программирования, является принцип оптимальности, суть которого заключается в том, что каждое последующее решение строится оптимальным образом независимо от решений, получаемых на всех предыдущих этапах, кроме последнего. Чтобы реализовать этот принцип, необходимо в исходной задаче определить:
? этапы решений (подзадачи, на которые она декомпозируется);
? управляемые переменные (варианты решений) на каждом этапе;
? информацию для решения задачи на каждом этапе;
? рекуррентные вычислительные процедуры, связывающие соседние этапы.
Другими словами, в методе динамического программирования искус-твенно создаются условия для независимой оптимизации на отдельном г по результатам только предыдущего, причем с гарантией того, что «ученное решение будет находиться в области допустимых.
Различают прямые и обратные методы оптимизации. Они отличаются ДРУГ от друга различным представлением переменной и видом рекуррентных соотношений (см. [6.51]).
Похожие рефераты:
